In order to manage a large collection of data elements, it is common to organize the data elements in some hierarchical order or sequence. With such organization, each data element has a unique location in the sequence and becomes more readily accessible. Further, a sequential reading of all the elements is made possible.
In the case of an indexed sequential file system or an indexed sequential access method (ISAM), a large collection of records is organized in "key number" order. That is, each record is associated with a unique key number and the key numbers are arranged in ascending order. Hence, each record may be retrieved either by individual key number or sequentially (i.e. in order of ascending key number). The key numbers and records are considered to be elements of the file.
Indexed sequential files are usually implemented in a computer or software system using a data structure known as a B tree. In general, a B tree comprises a set of vertices called nodes connected by a set of branches called pointers. Each node holds a unique set of ordered key numbers. The nodes are arranged in an order themselves. In order to read or search the B tree, one sequentially traverses the tree from node to node via the pointers. One node is designated as "root", and the B-tree is said to be "oriented" such that a unique path of pointers leads from the root to each of the remaining nodes. A node which is pointed to by a pointer from another node is considered to be a descendant node. A node with no descendants is called a "leaf node".
Each leaf node contains N key numbers (keys) sorted in ascendancy order together with N associating data values or records of the indexed sequential file.
Each non-leaf node contains a series of N key numbers (keys) or elements sorted in ascending order plus N associated pointers. The pointer associated with the Ith key points to a subtree which contains all nodes whose elements are greater than or equal to the I-th key and less than the I+1 key.
Each node in the tree (with the exception of the root) is at least half full.
A user is able to operate on a B-tree in the following three ways.